// https://leetcode.cn/problems/binary-tree-maximum-path-sum/
// Created by ade on 2022/8/15.
// 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。
// 同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
//
// 路径和 是路径中各节点值的总和。
//
// 给你一个二叉树的根节点 root ，返回其 最大路径和 。
/*
 *                                               1
 *                                      2                3
 *                                 4        5        6        7
 *                              8     9  10   11  12   13  14   15
 *
 *
 
最笨的方法是找出左边链做大值和右边链最大值，相加取得最大值。坏处是需要递归两次，空间复杂度是O(n),时间复杂度是2log(n)很不划算

官方解法：直接取出每个点的值，取最大值，空间复杂度O(1), 时间复杂度log(n),

 * */
#include <iostream>
#include <vector>
#include <unordered_map>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:

    unordered_map<TreeNode *, int> m;
    int maxInt = INT_MIN;

    int maxPathSum1(TreeNode *root) {
        dfs(root);
        for (auto i:m) {
            cout << i.first->val << "-" << i.second << endl;
        }
        dfs1(root);


        return maxInt;
    }

    int dfs(TreeNode *root) {
        if (!root) return 0;
        m[root] = max(max(dfs(root->left), dfs(root->right)) + root->val, root->val);
        return m[root];
    }

    void dfs1(TreeNode *root) {
        if (!root) return;
        maxInt = max(maxInt, m[root->left] + m[root->right] + root->val);
		maxInt = max(maxInt, m[root->right] + root->val);
        maxInt = max(maxInt, m[root->left] + root->val);
        maxInt = max(maxInt, root->val);
        dfs1(root->left);
        dfs1(root->right);
    }

    TreeNode *init() {
        TreeNode *t1 = new TreeNode(9);
        TreeNode *t2 = new TreeNode(6);
		TreeNode *t3 = new TreeNode(-3);
		TreeNode *t4 = new TreeNode(-6);
		TreeNode *t5 = new TreeNode(2);
		TreeNode *t6 = new TreeNode(2);
		TreeNode *t7 = new TreeNode(-6);
		TreeNode *t8 = new TreeNode(-6);
		TreeNode *t9 = new TreeNode(-6);
        t1->left = t2;
		t1->right = t3;
		t2->left = t4;
		t2->right = t5;
		t5->left = t6;
		t6->left = t7;
		t7->left = t9;
		t6->right = t7;
        return t1;
    }
	
	
	// 官方解法
	int maxS = INT_MIN;
	int maxPathSum(TreeNode *root) {
        maxNode(root);
		return maxS;
    }
	
	int maxNode(TreeNode * node){
		if(!node) return 0;
		int left = max(maxNode(node->left), 0);
		int right = max(maxNode(node->right), 0);
		int nodeVal = node->val + left + right;
		maxS = max(nodeVal, maxS);
		return node->val + max(left, right);
	}
};

int main() {
    Solution so;
    TreeNode *t = so.init();
    cout << so.maxPathSum(t) << endl;
    return 0;
}